// Copyright (C) 1986-1997 by Symantec
// Copyright (C) 2000-2009 by Digital Mars
// All Rights Reserved
// http://www.digitalmars.com
// Written by Walter Bright
/*
 * This source file is made available for personal use
 * only. The license is in /dmd/src/dmd/backendlicense.txt
 * For any other uses, please contact Digital Mars.
 */


/****************************************************************
 * Handle basic blocks.
 */

#if !SPP

#include	<stdio.h>
#include	<string.h>
#include	<time.h>
#include	"cc.h"
#include	"oper.h"
#include	"el.h"
#include	"type.h"
#include	"global.h"
#include	"parser.h"
#include	"go.h"
#include	"code.h"
#if SCPP
#if TX86
#include	"iasm.h"
#else
#include	"TG.h"
#endif
#endif

static char __file__[] = __FILE__;	/* for tassert.h		*/
#include	"tassert.h"

STATIC void bropt(void);
STATIC void brrear(void);
STATIC void search(block *b);
STATIC void elimblks(void);
STATIC int  mergeblks(void);
STATIC void blident(void);
STATIC void blreturn(void);
STATIC void brmin(void);
STATIC void bltailmerge(void);
STATIC void block_check();
STATIC void brtailrecursion();
STATIC elem * assignparams(elem **pe,int *psi,elem **pe2);
STATIC void emptyloops();
int el_anyframeptr(elem *e);
	    
#if TX86
unsigned numblks;	// number of basic blocks in current function
block *startblock;	/* beginning block of function			*/
			/* (can have no predecessors)			*/

block **dfo = NULL;	/* array of depth first order			*/
unsigned dfotop;	/* # of items in dfo[]				*/

block *curblock;	/* current block being read in			*/
block *block_last;	// last block read in

#endif

static block * block_freelist;

////////////////////////////
// Storage allocator.

static block blkzero;

__inline block *block_calloc_i()
{   block *b;

    if (block_freelist)
    {	b = block_freelist;
	block_freelist = b->Bnext;
	*b = blkzero;
    }
    else
	b = (block *) mem_fcalloc(sizeof(block));
    return b;
}

block *block_calloc()
{
    return block_calloc_i();
}

//////////////////////////////////
//

unsigned bc_goal[BCMAX];

void block_init()
{   int i;

    for (i = 0; i < BCMAX; i++)
	bc_goal[i] = GOALvalue;
    bc_goal[BCgoto] = GOALnone;
    bc_goal[BCret ] = GOALnone;
    bc_goal[BCexit] = GOALnone;
}

//////////////////////////////////
//

void block_term()
{
#if TERMCODE
    block *b;

    while (block_freelist)
    {	b = block_freelist->Bnext;
	mem_ffree(block_freelist);
	block_freelist = b;
    }

#endif
}

/**************************
 * Finish up this block and start the next one.
 */

#if MARS
void block_next(Blockx *bctx,enum BC bc,block *bn)
{
    bctx->curblock->BC = bc;
    block_last = bctx->curblock;
    if (!bn)
	bn = block_calloc_i();
    bctx->curblock->Bnext = bn;			// next block
    bctx->curblock = bctx->curblock->Bnext;	// new current block
#if NTEXCEPTIONS
    bctx->curblock->Btry = bctx->tryblock;
#endif
    bctx->curblock->Bflags |= bctx->flags;
}
#else
void block_next(enum BC bc,block *bn)
{
    curblock->BC = bc;
    curblock->Bsymend = globsym.top;
    block_last = curblock;
    if (!bn)
	bn = block_calloc_i();
    curblock->Bnext = bn;			// next block
    curblock = curblock->Bnext;		// new current block
    curblock->Bsymstart = globsym.top;
    curblock->Btry = pstate.STbtry;
}

void block_next()
{
    block_next((enum BC)curblock->BC,NULL);
}
#endif

/**************************
 * Finish up this block and start the next one.
 */

#if MARS

block *block_goto(Blockx *bx,enum BC bc,block *bn)
{   block *b;

    b = bx->curblock;
    block_next(bx,bc,bn);
    list_append(&b->Bsucc,bx->curblock);
    return bx->curblock;
}

#endif

/****************************
 * Goto a block named gotolbl.
 * Start a new block that is labelled by newlbl.
 */

#if SCPP

void block_goto()
{
    block_goto(block_calloc());
}

void block_goto(block *bn)
{
    block_goto(bn,bn);
}

void block_goto(block *bgoto,block *bnew)
{
    enum BC bc;

    assert(bgoto);
    list_append(&(curblock->Bsucc),bgoto);
    if (curblock->Bcode)	// If there is already code in the block
				// then this is an ASM block
	    bc = BCasm;
    else
	    bc = BCgoto;	// fall thru to next block
    block_next(bc,bnew);
}

#endif

/**********************************
 * Replace block numbers with block pointers.
 * Also compute numblks and maxblks.
 */

void block_ptr()
{   block *b;
    unsigned i;

/*    dbg_printf("block_ptr()\n");*/

    numblks = 0;
    for (b = startblock; b; b = b->Bnext)	/* for each block	 */
    {
#if SCPP
	b->Bblknum = numblks;
#endif
	numblks++;
    }
    maxblks = 3 * numblks;		/* allow for increase in # of blocks */
}

/*******************************
 * Build predecessor list (Bpred) for each block.
 */

void block_pred()
{   block *b;

    //dbg_printf("block_pred()\n");
    for (b = startblock; b; b = b->Bnext)	/* for each block	 */
	list_free(&b->Bpred,FPNULL);

    for (b = startblock; b; b = b->Bnext)	/* for each block	 */
    {	register list_t bp;

	//printf("b = %p, BC = ",b); WRBC(b->BC); printf("\n");
	for (bp = b->Bsucc; bp; bp = list_next(bp))
	{				/* for each successor to b	*/
		//printf("\tbs = %p\n",list_block(bp));
		assert(list_block(bp));
		list_prepend(&(list_block(bp)->Bpred),b);
	}
    }
    assert(startblock->Bpred == NULL);	/* startblock has no preds	*/
}

/********************************************
 * Clear visit.
 */

void block_clearvisit()
{   block *b;

    for (b = startblock; b; b = b->Bnext)	// for each block
	b->Bflags &= ~BFLvisited;		// mark as unvisited
}

/********************************************
 * Visit block and each of its predecessors.
 */

void block_visit(block *b)
{   list_t l;

    b->Bflags |= BFLvisited;
    for (l = b->Bsucc; l; l = list_next(l))	 // for each successor
    {	block *bs = list_block(l);
	assert(bs);
	if ((bs->Bflags & BFLvisited) == 0)	// if not visited
	    block_visit(bs);
    }
}

/*****************************
 * Compute number of parents (Bcount) of each basic block.
 */

void block_compbcount()
{   block *b;
    list_t bl;
    int again;

    block_clearvisit();
    block_visit(startblock);			// visit all reachable blocks
    elimblks();					// eliminate unvisited blocks
}

/*******************************
 * Free list of blocks.
 */

void blocklist_free(block **pb)
{	block *b,*bn;

	for (b = *pb; b; b = bn)
	{	bn = b->Bnext;
		block_free(b);
	}
	*pb = NULL;
}

/********************************
 * Free optimizer gathered data.
 */

void block_optimizer_free(block *b)
{
    vec_free(b->Bdom);
    vec_free(b->Binrd);
    vec_free(b->Boutrd);
    vec_free(b->Binlv);
    vec_free(b->Boutlv);
    vec_free(b->Bin);
    vec_free(b->Bout);
    vec_free(b->Bgen);
    vec_free(b->Bkill);
    vec_free(b->Bout2);
    vec_free(b->Bgen2);
    vec_free(b->Bkill2);

#if TX86
    memset(&b->_BLU,0,sizeof(b->_BLU));
#else
    memset(&b->_BLU.BLCG,0,sizeof(b->_BLU.BLCG));
#endif
}

/****************************
 * Free a block.
 */

void block_free(block *b)
{
    assert(b);
    if (b->Belem)
	el_free(b->Belem);
    list_free(&b->Bsucc,FPNULL);
    list_free(&b->Bpred,FPNULL);
    if (OPTIMIZER)
	block_optimizer_free(b);
    switch (b->BC)
    {   case BCswitch:
	case BCifthen:
	case BCjmptab:
	    MEM_PH_FREE(b->BS.Bswitch);
	    break;
#if SCPP
	case BCcatch:
	    type_free(b->Bcatchtype);
	    break;
#endif
	case BCasm:
	    code_free(b->Bcode);
	    break;
    }
    b->Bnext = block_freelist;
    block_freelist = b;
}

/****************************
 * Hydrate/dehydrate a list of blocks.
 */

#if HYDRATE
void blocklist_hydrate(block **pb)
{   block *b;

    while (isdehydrated(*pb))
    {
	/*dbg_printf("blocklist_hydrate(*pb = %p) =",*pb);*/
	b = (block *)ph_hydrate(pb);
	/*dbg_printf(" %p\n",b);*/
	el_hydrate(&b->Belem);
	list_hydrate(&b->Bsucc,FPNULL);
	list_hydrate(&b->Bpred,FPNULL);
	(void) ph_hydrate(&b->Btry);
#if SCPP
	(void) ph_hydrate(&b->Bendscope);
	symbol_hydrate(&b->Binitvar);
#endif
	switch (b->BC)
	{
#if SCPP
	    case BCtry:
		symbol_hydrate(&b->catchvar);
		break;
	    case BCcatch:
		type_hydrate(&b->Bcatchtype);
		break;
#endif
	    case BCswitch:
		(void) ph_hydrate(&b->BS.Bswitch);
		break;

	    case BC_finally:
		//(void) ph_hydrate(&b->B_ret);
		break;

	    case BCasm:
		code_hydrate(&b->Bcode);
		break;
	}
#if TX86
	filename_translate(&b->Bsrcpos);
	srcpos_hydrate(&b->Bsrcpos);
#endif
	pb = &b->Bnext;
    }
}
#endif

#if DEHYDRATE
void blocklist_dehydrate(block **pb)
{   block *b;

    while ((b = *pb) != NULL && !isdehydrated(b))
    {
#if DEBUG_XSYMGEN
	if (xsym_gen && ph_in_head(b))
	    return;
#endif
	/*dbg_printf("blocklist_dehydrate(*pb = %p) =",b);*/
	ph_dehydrate(pb);
	/*dbg_printf(" %p\n",*pb);*/
	el_dehydrate(&b->Belem);
	list_dehydrate(&b->Bsucc,FPNULL);
	list_dehydrate(&b->Bpred,FPNULL);
	ph_dehydrate(&b->Btry);
#if SCPP
	ph_dehydrate(&b->Bendscope);
	symbol_dehydrate(&b->Binitvar);
#endif
	switch (b->BC)
	{
#if SCPP
	    case BCtry:
		symbol_dehydrate(&b->catchvar);
		break;
	    case BCcatch:
		type_dehydrate(&b->Bcatchtype);
		break;
#endif
	    case BCswitch:
		ph_dehydrate(&b->BS.Bswitch);
		break;

	    case BC_finally:
		//ph_dehydrate(&b->B_ret);
		break;

	    case BCasm:
		code_dehydrate(&b->Bcode);
		break;
	}
#if TX86
	srcpos_dehydrate(&b->Bsrcpos);
#endif
	pb = &b->Bnext;
    }
}
#endif

/****************************
 * Append elem to the elems comprising the current block.
 * Read in an expression and put it in curblock->Belem.
 * If there is one already there, create a tree like:
 *		,
 *	       / \
 *	     old  e
 */

void block_appendexp(block *b,elem *e)
{   elem *ec;
    elem **pe;

    assert(MARS || PARSER);
    if (e)
    {
	assert(b);
	elem_debug(e);
	pe = &b->Belem;
	ec = *pe;
	if (ec != NULL)
	{
#if MARS
	    tym_t ty = e->Ety;
	    targ_size_t enumbytes = e->Enumbytes;

	    elem_debug(e);
	    /* Build tree such that (a,b) => (a,(b,e))	*/
	    while (ec->Eoper == OPcomma)
	    {
		ec->Ety = ty;
		ec->Enumbytes = enumbytes;
		pe = &(ec->E2);
		ec = *pe;
	    }
	    e = el_bin(OPcomma,ty,ec,e);
	    e->Enumbytes = enumbytes;
#else
	    type *t = e->ET;

	    type_debug(t);
	    elem_debug(e);
	    /* Build tree such that (a,b) => (a,(b,e))	*/
	    while (ec->Eoper == OPcomma)
	    {
		el_settype(ec,t);
		pe = &(ec->E2);
		ec = *pe;
	    }
	    e = el_bint(OPcomma,t,ec,e);
#endif
	}
	*pe = e;
    }
}

/************************
 * Mark curblock as initializing symbol s.
 */

#if SCPP

#undef block_initvar

void block_initvar(symbol *s)
{
#ifdef DEBUG
    assert(curblock);
#endif
    symbol_debug(s);
    curblock->Binitvar = s;
}

#endif

/*******************
 * Mark end of function.
 * flag:
 *	0	do a "return"
 *	1	do a "return 0"
 */

void block_endfunc(int flag)
{
#if SCPP
    curblock->Bsymend = globsym.top;
    curblock->Bendscope = curblock;
#endif
    if (flag)
    {	elem *e;

	e = el_longt(tsint, 0);
	block_appendexp(curblock, e);
	curblock->BC = BCretexp;	// put a return at the end
    }
    else
	curblock->BC = BCret;		// put a return at the end
    curblock = NULL;			// undefined from now on
    block_last = NULL;
}

/******************************
 * Perform branch optimization on basic blocks.
 */

void blockopt(int iter)
{   block *b;
    int count;

    if (OPTIMIZER)
    {
	count = 0;
	do
	{
	    //printf("changes = %d, count = %d, dfotop = %d\n",changes,count,dfotop);
#if MARS
	    util_progress();
#else
	    if (controlc_saw)
		util_exit(EXIT_BREAK);
#endif
	    changes = 0;
	    bropt();			// branch optimization
	    brrear();			// branch rearrangement
	    blident();			// combine identical blocks
	    blreturn();			// split out return blocks
	    bltailmerge();		// do tail merging
	    brtailrecursion();		// do tail recursion
	    brcombine();		// convert graph to expressions
	    if (iter >= 2)
		brmin();		// minimize branching
	    do
	    {
		compdfo();		/* compute depth first order (DFO) */
		elimblks();		/* remove blocks not in DFO	 */
		assert(count < 200);
		count++;
	    } while (mergeblks());	/* merge together blocks	 */
	} while (changes);
#ifdef DEBUG
	if (debugw)
	    for (b = startblock; b; b = b->Bnext)
		WRblock(b);
#endif
    }
    else
    {
	/* canonicalize the trees	 */
	for (b = startblock; b; b = b->Bnext)
	{
#ifdef DEBUG
	    if (debugb)
		WRblock(b);
#endif
	    if (b->Belem)
	    {	b->Belem = doptelem(b->Belem,bc_goal[b->BC] | GOALstruct);
		if (b->Belem)
		    b->Belem = el_convert(b->Belem);
	    }
#ifdef DEBUG
	    if (debugb)
	    {	dbg_printf("after optelem():\n");
		WRblock(b);
	    }
#endif
	}
	if (localgot)
	{   // Initialize with:
	    //	localgot = OPgot;
	    elem *e = el_long(TYnptr, 0);
	    e->Eoper = OPgot;
	    e = el_bin(OPeq, TYnptr, el_var(localgot), e);
	    startblock->Belem = el_combine(e, startblock->Belem);
	}

	bropt();			/* branch optimization		 */
	brrear();			/* branch rearrangement		 */
	comsubs();			/* eliminate common subexpressions */
#ifdef DEBUG
	if (debugb)
		for (b = startblock; b; b = b->Bnext)
			WRblock(b);
#endif
    }
}

/***********************************
 * Try to remove control structure.
 * That is, try to resolve if-else, goto and return statements
 * into &&, || and ?: combinations.
 */

void brcombine()
{   block *b;
    block *b2,*b3;
    int op;
    int anychanges;

    cmes("brcombine()\n");
    //for (b = startblock; b; b = b->Bnext)
	//WRblock(b);

    if (funcsym_p->Sfunc->Fflags3 & (Fcppeh | Fnteh))
    {	// Don't mess up extra EH info by eliminating blocks
	return;
    }

    do
    {
	anychanges = 0;
	for (b = startblock; b; b = b->Bnext)	/* for each block	*/
	{   unsigned char bc;

	    /* Look for [e1 IFFALSE L3,L2] L2: [e2 GOTO L3] L3: [e3]	*/
	    /* Replace with [(e1 && e2),e3]				*/
	    bc = b->BC;
	    if (bc == BCiftrue)
	    {   unsigned char bc2,bc3;

		b2 = list_block(b->Bsucc);
		b3 = list_block(list_next(b->Bsucc));

		if (list_next(b2->Bpred))	// if more than one predecessor
		    continue;
		if (b2 == b3)
		    continue;
		if (b2 == startblock)
		    continue;
		if (!PARSER && b2->Belem && EOP(b2->Belem))
		    continue;

		bc2 = b2->BC;
		if (bc2 == BCgoto &&
		    b3 == list_block(b2->Bsucc))
		{
		    b->BC = BCgoto;
		    if (b2->Belem)
		    {
			op = OPandand;
			b->Belem = PARSER ? el_bint(op,tsint,b->Belem,b2->Belem)
					  : el_bin(op,TYint,b->Belem,b2->Belem);
			b2->Belem = NULL;
		    }
		    list_subtract(&(b->Bsucc),b2);
		    list_subtract(&(b2->Bpred),b);
		    cmes("brcombine(): if !e1 then e2 => e1 || e2\n");
		    anychanges++;
		}
		else if (list_next(b3->Bpred) || b3 == startblock)
		    continue;
		else if ((bc2 == BCretexp && b3->BC == BCretexp)
			 //|| (bc2 == BCret && b3->BC == BCret)
			)
		{   elem *e;

		    if (PARSER)
		    {	type *t;

			t = (bc2 == BCretexp) ? b2->Belem->ET : tsvoid;
			e = el_bint(OPcolon2,t,b2->Belem,b3->Belem);
			b->Belem = el_bint(OPcond,t,b->Belem,e);
		    }
		    else
		    {	tym_t ty;

			if (EOP(b3->Belem))
			    continue;
			ty = (bc2 == BCretexp) ? b2->Belem->Ety : TYvoid;
			e = el_bin(OPcolon2,ty,b2->Belem,b3->Belem);
			b->Belem = el_bin(OPcond,ty,b->Belem,e);
		    }
		    b->BC = bc2;
		    b2->Belem = NULL;
		    b3->Belem = NULL;
		    list_free(&b->Bsucc,FPNULL);
		    list_subtract(&(b2->Bpred),b);
		    list_subtract(&(b3->Bpred),b);
		    cmes("brcombine(): if e1 return e2 else return e3 => ret e1?e2:e3\n");
		    anychanges++;
		}
		else if (bc2 == BCgoto &&
			 b3->BC == BCgoto &&
			 list_block(b2->Bsucc) == list_block(b3->Bsucc))
		{   elem *e;
		    block *bsucc;

		    bsucc = list_block(b2->Bsucc);
		    if (b2->Belem)
		    {
			if (PARSER)
			{
			    if (b3->Belem)
			    {
				e = el_bint(OPcolon2,b2->Belem->ET,
					b2->Belem,b3->Belem);
				e = el_bint(OPcond,e->ET,b->Belem,e);
			    }
			    else
			    {
				op = OPandand;
				e = el_bint(op,tsint,b->Belem,b2->Belem);
			    }
			}
			else
			{
			    if (b3->Belem)
			    {
				if (EOP(b3->Belem))
				    continue;
				e = el_bin(OPcolon2,b2->Belem->Ety,
					b2->Belem,b3->Belem);
				e = el_bin(OPcond,e->Ety,b->Belem,e);
			    }
			    else
			    {
				op = OPandand;
				e = el_bin(op,TYint,b->Belem,b2->Belem);
			    }
			}
			b2->Belem = NULL;
			b->Belem = e;
		    }
		    else if (b3->Belem)
		    {
			op = OPoror;
			b->Belem = PARSER ? el_bint(op,tsint,b->Belem,b3->Belem)
					  : el_bin(op,TYint,b->Belem,b3->Belem);
		    }
		    b->BC = BCgoto;
		    b3->Belem = NULL;
		    list_free(&b->Bsucc,FPNULL);

		    list_append(&b->Bsucc,bsucc);
		    list_append(&bsucc->Bpred,b);

		    list_free(&(b2->Bpred),FPNULL);
		    list_free(&(b2->Bsucc),FPNULL);
		    list_free(&(b3->Bpred),FPNULL);
		    list_free(&(b3->Bsucc),FPNULL);
		    b2->BC = BCret;
		    b3->BC = BCret;
		    list_subtract(&(bsucc->Bpred),b2);
		    list_subtract(&(bsucc->Bpred),b3);
		    cmes("brcombine(): if e1 goto e2 else goto e3 => ret e1?e2:e3\n");
		    anychanges++;
		}
	    }
	    else if (bc == BCgoto && PARSER)
	    {
		b2 = list_block(b->Bsucc);
		if (!list_next(b2->Bpred) && b2->BC != BCasm	// if b is only parent
		    && b2 != startblock
#if SCPP
		    && b2->BC != BCtry
#endif
		    && b2->BC != BC_try
		    && b->Btry == b2->Btry
		   )
		{   list_t bl;

		    if (b2->Belem)
		    {
			if (PARSER)
			{
			    block_appendexp(b,b2->Belem);
			}
			else if (b->Belem)
			    b->Belem = el_bin(OPcomma,b2->Belem->Ety,b->Belem,b2->Belem);
			else
			    b->Belem = b2->Belem;
			b2->Belem = NULL;
		    }
		    list_subtract(&b->Bsucc,b2);
		    list_subtract(&b2->Bpred,b);

		    /* change predecessor of successors of b2 from b2 to b */
		    for (bl = b2->Bsucc; bl; bl = list_next(bl))
		    {	list_t bp;

			for (bp = list_block(bl)->Bpred; bp; bp = list_next(bp))
			{
			    if (list_block(bp) == b2)
				list_ptr(bp) = (void *)b;
			}
		    }

		    b->BC = b2->BC;
		    b->BS = b2->BS;
		    b->Bsucc = b2->Bsucc;
		    b2->Bsucc = NULL;
		    b2->BC = BCret;		/* a harmless one	*/
		    cmes3("brcombine(): %p goto %p eliminated\n",b,b2);
		    anychanges++;
		}
	    }
	}
	if (anychanges)
	{   changes++;
	    continue;
	}
    } while (0);
}

/***********************
 * Branch optimization.
 */

STATIC void bropt()
{	block *b,*db;
	elem *n,**pn;

	cmes("bropt()\n");
	assert(!PARSER);
	for (b = startblock; b; b = b->Bnext)	/* for each block	*/
	{
		pn = &(b->Belem);
		if (OPTIMIZER && *pn)
		    while ((*pn)->Eoper == OPcomma)
			pn = &((*pn)->E2);

		n = *pn;
		if (b->BC == BCiftrue)
		{
			assert(n);
			/* Replace IF (!e) GOTO ... with	*/
			/* IF OPnot (e) GOTO ...		*/
			if (n->Eoper == OPnot)
			{
			    tym_t tym;

			    tym = n->E1->Ety;
			    *pn = el_selecte1(n);
			    (*pn)->Ety = tym;
			    for (n = b->Belem; n->Eoper == OPcomma; n = n->E2)
				n->Ety = tym;
			    b->Bsucc = list_reverse(b->Bsucc);
			    cmes("CHANGE: if (!e)\n");
			    changes++;
			}

			/* Take care of IF (constant)			*/
			if (iftrue(n))		/* if elem is TRUE	*/
			{
			    // select first succ
			    db = list_block(list_next(b->Bsucc));
			    goto L1;
			}
			else if (iffalse(n))
			{
			    // select second succ
			    db = list_block(b->Bsucc);

			    L1:	list_subtract(&(b->Bsucc),db);
				list_subtract(&(db->Bpred),b);
				b->BC = BCgoto;
				/* delete elem if it has no side effects */
				b->Belem = doptelem(b->Belem,GOALnone | GOALagain);
				cmes("CHANGE: if (const)\n");
				changes++;
			}

			/* Look for both destinations being the same	*/
			else if (list_block(b->Bsucc) ==
				 list_block(list_next(b->Bsucc)))
			{	b->BC = BCgoto;
				db = list_block(b->Bsucc);
				list_subtract(&(b->Bsucc),db);
				list_subtract(&(db->Bpred),b);
				cmes("CHANGE: if (e) goto L1; else goto L1;\n");
				changes++;
			}
		}
		else if (b->BC == BCswitch)
		{	/* see we can evaluate this switch now	*/
			register unsigned i,ncases;
			targ_llong *p,value;
			register list_t bl;

			while (n->Eoper == OPcomma)
				n = n->E2;
			if (n->Eoper != OPconst)
				continue;
			assert(tyintegral(n->Ety));
			value = el_tolong(n);
			p = b->BS.Bswitch;	/* ptr to switch data	*/
			assert(p);
			ncases = *p++;		/* # of cases		*/
			i = 1;			/* first case		*/
			while (1)
			{
				if (i > ncases)
				{   i = 0;	/* select default	*/
				    break;
				}
				if (*p++ == value)
				    break;	/* found it		*/
				i++;		/* next case		*/
			}
			/* the ith entry in Bsucc is the one we want	*/
			db = list_block(list_nth(b->Bsucc,i));
			/* delete predecessors of successors (!)	*/
			for (bl = b->Bsucc; bl; bl = list_next(bl))
			    if (i--)		// if not ith successor
			    {	void *p;
				p = list_subtract(
				    &(list_block(bl)->Bpred),b);
				assert(p == b);
			    }

			/* dump old successor list and create a new one	*/
			list_free(&b->Bsucc,FPNULL);
			list_append(&b->Bsucc,db);
			b->BC = BCgoto;
#if !HOST_THINK
			MEM_PH_FREE(b->BS.Bswitch);
#endif
			b->Belem = doptelem(b->Belem,GOALnone | GOALagain);
			cmes("CHANGE: switch (const)\n");
			changes++;
		}
	}
}

/*********************************
 * Do branch rearrangement.
 */

STATIC void brrear()
{	register block *b;

	cmes("brrear()\n");
	for (b = startblock; b; b = b->Bnext)	/* for each block	*/
	{	register list_t bl;

		for (bl = b->Bsucc; bl; bl = list_next(bl))
		{	/* For each transfer of control block pointer	*/
			block *bt;
			int iter = 0;

			bt = list_block(bl);

			/* If it is a transfer to a block that consists	*/
			/* of nothing but an unconditional transfer,	*/
			/*	Replace transfer address with that	*/
			/*	transfer address.			*/
			/* Note: There are certain kinds of infinite	*/
			/* loops which we avoid by putting a lid on	*/
			/* the number of iterations.			*/

			while (bt->BC == BCgoto && !bt->Belem &&
#if SCPP || NTEXCEPTIONS
				b->Btry == bt->Btry &&
#endif
#if NTEXCEPTIONS
				bt->Btry == list_block(bt->Bsucc)->Btry &&
#endif

			       ++iter < T68000(numblks) T80x86(10))
			{
				list_ptr(bl) = list_ptr(bt->Bsucc);
				if (bt->Bsrcpos.Slinnum && !b->Bsrcpos.Slinnum)
				    b->Bsrcpos = bt->Bsrcpos;
				b->Bflags |= bt->Bflags;
				list_append(&(list_block(bl)->Bpred),b);
				list_subtract(&(bt->Bpred),b);
				cmes("goto->goto\n");
				bt = list_block(bl);
			}

			// Bsucc after the first are the targets of
			// jumps, calls and loops, and as such to do this right
			// we need to traverse the Bcode list and fix up
			// the IEV2.Vblock pointers.
			if (b->BC == BCasm)
			    break;
		}
#if 0
		/* Replace cases of			*/
		/*	IF (e) GOTO L1 ELSE L2		*/
		/*	L1:				*/
		/* with					*/
		/*	IF OPnot (e) GOTO L2 ELSE L1	*/
		/*	L1:				*/

		if (b->BC == BCiftrue || b->BC == BCiffalse)
		{	register block *bif,*belse;

			bif = list_block(b->Bsucc);
			belse = list_block(list_next(b->Bsucc));

			if (bif == b->Bnext)
			{	b->BC ^= BCiffalse ^ BCiftrue;	/* toggle */
				list_ptr(b->Bsucc) = belse;
				list_ptr(list_next(b->Bsucc)) = bif;
				b->Bflags |= bif->Bflags & BFLvisited;
				cmes("if (e) L1 else L2\n");
			}
		}
#endif
	} /* for */
}

/*************************
 * Compute depth first order (DFO).
 * Equivalent to Aho & Ullman Fig. 13.8.
 * Blocks not in dfo[] are unreachable.
 */

void compdfo()
{ register block *b;
  register int i;

  cmes("compdfo()\n");
  assert(OPTIMIZER);
  block_clearvisit();
#ifdef DEBUG
  if (maxblks == 0 || maxblks < numblks)
	dbg_printf("maxblks = %d, numblks = %d\n",maxblks,numblks);
#endif
  assert(maxblks && maxblks >= numblks);
  debug_assert(!PARSER);
  if (!dfo)
#if TX86
	dfo = (block **) util_calloc(sizeof(block *),maxblks);
#else
	dfo = (block **) MEM_PARF_CALLOC(sizeof(block *) * maxblks);
#endif
  dfotop = numblks;			/* assign numbers backwards	*/
  search(startblock);
  assert(dfotop <= numblks);
  /* Ripple data to the bottom of the array	*/
  if (dfotop)				/* if not at bottom		*/
  {	for (i = 0; i < numblks - dfotop; i++)
	{	dfo[i] = dfo[i + dfotop];
		dfo[i]->Bdfoidx = i;
	}
  }
  dfotop = numblks - dfotop;
#if 0
  for (i = 0; i < dfotop; i++)
	dbg_printf("dfo[%d] = 0x%x\n",i,dfo[i]);
#endif
}

/******************************
 * Add block to dfo[], then its successors.
 */

STATIC void search(block *b)
{ list_t l;

  assert(b);
  b->Bflags |= BFLvisited;		// executed at least once
  for (l = b->Bsucc; l; l = list_next(l))		// for each successor
  {	block *bs = list_block(l);

	assert(bs);
	if ((bs->Bflags & BFLvisited) == 0) // if not visited
	    search(bs);			// search it
  }
  dfo[--dfotop] = b;			// add to dfo[]
  b->Bdfoidx = dfotop;			// link back
}

/*************************
 * Remove blocks not marked as visited (they aren't in dfo[]).
 * A block is not in dfo[] if not visited.
 */

STATIC void elimblks()
{   block **pb,*b;
    list_t s;
    block *bf;

#ifdef DEBUG
    if (OPTIMIZER)
    {	int n;

	n = 0;
	for (b = startblock; b; b = b->Bnext)
	      n++;
	//dbg_printf("1 n = %d, numblks = %d, dfotop = %d\n",n,numblks,dfotop);
	assert(numblks == n);
    }
#endif

    cmes("elimblks()\n");
    bf = NULL;
    for (pb = &startblock; (b = *pb) != NULL;)
    {
	if (((b->Bflags & BFLvisited) == 0)  /* if block is not visited	*/
	    && ((b->Bflags & BFLlabel) == 0)	/* need label offset	*/
	    )
	{
		/* for each marked successor S to b			*/
		/*	remove b from S.Bpred.				*/
		/* Presumably all predecessors to b are unmarked also.	*/
		for (s = b->Bsucc; s; s = list_next(s))
		{   assert(list_block(s));
		    if (list_block(s)->Bflags & BFLvisited) /* if it is marked */
			list_subtract(&(list_block(s)->Bpred),b);
		}
		if (b->Balign && b->Bnext && b->Balign > b->Bnext->Balign)
		    b->Bnext->Balign = b->Balign;
		*pb = b->Bnext;		/* remove from linked list	*/

		b->Bnext = bf;
		bf = b;			/* prepend to deferred list to free */
		cmes2("CHANGE: block %p deleted\n",b);
		changes++;
	}
	else
		pb = &((*pb)->Bnext);
    }

    // Do deferred free's of the blocks
    for ( ; bf; bf = b)
    {	b = bf->Bnext;
	block_free(bf);
	numblks--;
    }

    cmes("elimblks done\n");
    assert(!OPTIMIZER || numblks == dfotop);
}

/**********************************
 * Merge together blocks where the first block is a goto to the next
 * block and the next block has only the first block as a predecessor.
 * Example:
 *	e1; GOTO L2;
 *	L2: return e2;
 * becomes:
 *	L2: return (e1 , e2);
 * Returns:
 *	# of merged blocks
 */

STATIC int mergeblks()
{	int merge = 0,i;

	assert(OPTIMIZER);
	cmes("mergeblks()\n");
	for (i = 0; i < dfotop; i++)
	{	block *b;

		b = dfo[i];
		if (b->BC == BCgoto)
		{   block *bL2 = list_block(b->Bsucc);

		    if (b == bL2)
		    {
		Lcontinue:
			continue;
		    }
		    assert(bL2->Bpred);
		    if (!list_next(bL2->Bpred) && bL2 != startblock)
		    {	list_t bl;
			elem *e;

			if (b == bL2 || bL2->BC == BCasm)
			    continue;

			if (
#if SCPP
			    bL2->BC == BCtry ||
#endif
			    bL2->BC == BC_try ||
			    b->Btry != bL2->Btry)
			    continue;
#if SCPP
			// If any predecessors of b are BCasm, don't merge.
			for (bl = b->Bpred; bl; bl = list_next(bl))
			{
			    if (list_block(bl)->BC == BCasm)
				goto Lcontinue;
			}
#endif

			/* JOIN the elems		*/
			e = el_combine(b->Belem,bL2->Belem);
			if (b->Belem && bL2->Belem)
			    e = doptelem(e,bc_goal[bL2->BC] | GOALagain);
			bL2->Belem = e;
			b->Belem = NULL;

			/* Remove b from predecessors of bL2	*/
			list_free(&(bL2->Bpred),FPNULL);
			bL2->Bpred = b->Bpred;
			b->Bpred = NULL;
			/* Remove bL2 from successors of b	*/
			list_free(&b->Bsucc,FPNULL);

			/* fix up successor list of predecessors	*/
			for (bl = bL2->Bpred; bl; bl = list_next(bl))
			{   register list_t bs;

			    for (bs=list_block(bl)->Bsucc; bs; bs=list_next(bs))
				if (list_block(bs) == b)
				    list_ptr(bs) = (void *)bL2;
			}

			merge++;
			cmes3("block %p merged with %p\n",b,bL2);

			if (b == startblock)
			{   /* bL2 is the new startblock */
			    block **pb;

			    cmes("bL2 is new startblock\n");
			    /* Remove bL2 from list of blocks	*/
			    for (pb = &startblock; 1; pb = &(*pb)->Bnext)
			    {	assert(*pb);
				if (*pb == bL2)
				{   *pb = bL2->Bnext;
				    break;
				}
			    }

			    /* And relink bL2 at the start		*/
			    bL2->Bnext = startblock->Bnext;
			    startblock = bL2;	/* new start		*/

			    block_free(b);
			    numblks--;
			    break;		/* dfo[] is now invalid	*/
			}
		    }
		}
	}
	return merge;
}

/*******************************
 * Combine together blocks that are identical.
 */

STATIC void blident()
{   block *bn;
    block *bnext;
    block *btry;

    cmes("blident()\n");
    assert(startblock);

#if SCPP
    // Determine if any asm blocks
    int anyasm = 0;
    for (bn = startblock; bn; bn = bn->Bnext)
    {	if (bn->BC == BCasm)
	{   anyasm = 1;
	    break;
	}
    }
#endif

    for (bn = startblock; bn; bn = bnext)
    {   block *b;

	bnext = bn->Bnext;
	if (bn->Bflags & BFLnomerg)
	    continue;

	for (b = bnext; b; b = b->Bnext)
	{
	    /* Blocks are identical if:			*/
	    /*	BC match				*/
	    /*  not optimized for time or it's a return	*/
	    /*	    (otherwise looprotate() is undone)	*/
	    /*  successors match			*/
	    /*  elems match				*/
	    if (b->BC == bn->BC &&
		//(!OPTIMIZER || !(mfoptim & MFtime) || !b->Bsucc) &&
		(!OPTIMIZER || !(b->Bflags & BFLnomerg) || !b->Bsucc) &&
		list_equal(b->Bsucc,bn->Bsucc) &&
#if SCPP || NTEXCEPTIONS
		b->Btry == bn->Btry &&
#endif
		el_match(b->Belem,bn->Belem)
	       )
	    {	/* Eliminate block bn		*/
		list_t bl;

		switch (b->BC)
		{
		    case BCswitch:
			if (memcmp(b->BS.Bswitch,bn->BS.Bswitch,list_nitems(bn->Bsucc) * sizeof(*bn->BS.Bswitch)))
			    continue;
			break;

#if SCPP
		    case BCtry:
		    case BCcatch:
#endif
#if MARS
		    case BCjcatch:
#endif
		    case BC_try:
		    case BC_finally:
		    case BCasm:
		    Lcontinue:
			continue;
		}
		assert(!b->Bcode);

		for (bl = bn->Bpred; bl; bl = list_next(bl))
		{   block *bp;

		    bp = list_block(bl);
		    if (bp->BC == BCasm)
			// Can't do this because of jmp's and loop's
			goto Lcontinue;
		}

#if 0 && SCPP
		// Predecessors must all be at the same btry level.
		if (bn->Bpred)
		{   block *bp;

		    bp = list_block(bn->Bpred);
		    btry = bp->Btry;
		    if (bp->BC == BCtry)
			btry = bp;
		}
		else
		    btry = NULL;

		for (bl = b->Bpred; bl; bl = list_next(bl))
		{   block *bp;

		    bp = list_block(bl);
		    if (bp->BC != BCtry)
			bp = bp->Btry;
		    if (btry != bp)
			goto Lcontinue;
		}
#endif

		// if bn is startblock, eliminate b instead of bn
		if (bn == startblock)
		{
		    goto Lcontinue;	// can't handle predecessors to startblock
		    bn = b;
		    b = startblock;		/* swap b and bn	*/
		}

#if SCPP
		// Don't do it if any predecessors are ASM blocks, since
		// we'd have to walk the code list to fix up any jmps.
		if (anyasm)
		{
		    for (bl = bn->Bpred; bl; bl = list_next(bl))
		    {   list_t bls;
			block *bp;

			bp = list_block(bl);
			if (bp->BC == BCasm)
			    goto Lcontinue;
			for (bls=bp->Bsucc; bls; bls=list_next(bls))
			    if (list_block(bls) == bn &&
				list_block(bls)->BC == BCasm)
				goto Lcontinue;
		    }
		}
#endif

		/* Change successors to predecessors of bn to point to	*/
		/* b instead of bn					*/
		for (bl = bn->Bpred; bl; bl = list_next(bl))
		{   list_t bls;
		    block *bp;

		    bp = list_block(bl);
		    for (bls=bp->Bsucc; bls; bls=list_next(bls))
			if (list_block(bls) == bn)
			{   list_ptr(bls) = (void *)b;
			    list_prepend(&b->Bpred,bp);
			}
		}

		/* Entirely remove predecessor list from bn.		*/
		/* elimblks() will delete bn entirely.			*/
		list_free(&(bn->Bpred),FPNULL);

#ifdef DEBUG
		assert(bn->BC != BCcatch);
		if (debugc)
		    dbg_printf("block B%d (%p) removed, it was same as B%d (%p)\n",
			bn->Bdfoidx,bn,b->Bdfoidx,b);
#endif
		changes++;
		break;
	    }
	}
    }
}

/**********************************
 * Split out return blocks so the returns can be combined into a
 * single block by blident().
 */

STATIC void blreturn()
{
    if (!(mfoptim & MFtime))		/* if optimized for space	*/
    {
	int retcount;			/* number of return counts	*/
	block *b;

	retcount = 0;

	/* Find last return block	*/
	for (b = startblock; b; b = b->Bnext)
	{   if (b->BC == BCret)
		retcount++;
	    if (b->BC == BCasm)
		return;			// mucks up blident()
	}

	if (retcount < 2)		/* quit if nothing to combine	*/
	    return;

	/* Split return blocks	*/
	for (b = startblock; b; b = b->Bnext)
	{   if (b->BC != BCret)
		continue;
#if SCPP || NTEXCEPTIONS
	    // If no other blocks with the same Btry, don't split
#if SCPP
	    if (config.flags3 & CFG3eh)
#endif
	    {
		for (block *b2 = startblock; b2; b2 = b2->Bnext)
		{
		    if (b2->BC == BCret && b != b2 && b->Btry == b2->Btry)
			goto L1;
		}
		continue;
	    }
	L1: ;
#endif
	    if (b->Belem)
	    {	/* Split b into a goto and a b	*/
		block *bn;

#ifdef DEBUG
		if (debugc)
		    dbg_printf("blreturn: splitting block B%d\n",b->Bdfoidx);
#endif
		numblks++;
		bn = block_calloc();
		bn->BC = BCret;
		bn->Bnext = b->Bnext;
#if SCPP || NTEXCEPTIONS
		bn->Btry = b->Btry;
#endif
		b->BC = BCgoto;
		b->Bnext = bn;
		list_append(&b->Bsucc,bn);
		list_append(&bn->Bpred,b);

		b = bn;
	    }
	}

	blident();			/* combine return blocks	*/
    }
}

/*****************************************
 * Convert expression into a list.
 * Construct the list in reverse, that is, so that the right-most
 * expression occurs first in the list.
 */

STATIC list_t bl_enlist(elem *e)
{   list_t el = NULL;

    if (e)
    {
	elem_debug(e);
	if (e->Eoper == OPcomma)
	{   list_t el2;
	    list_t pl;

	    el2 = bl_enlist(e->E1);
	    el = bl_enlist(e->E2);
	    e->E1 = e->E2 = NULL;
	    el_free(e);

	    /* Append el2 list to el	*/
	    assert(el);
	    for (pl = el; list_next(pl); pl = list_next(pl))
		;
	    list_next(pl) = el2;
	}
	else
	    list_prepend(&el,e);
    }
    return el;
}

/*****************************************
 * Take a list of expressions and convert it back into an expression tree.
 */

STATIC elem * bl_delist(list_t el)
{   elem *e;
    list_t elstart = el;

    for (e = NULL; el; el = list_next(el))
	e = el_combine(list_elem(el),e);
    list_free(&elstart,FPNULL);
    return e;
}

/*****************************************
 * Do tail merging.
 */

STATIC void bltailmerge()
{
    cmes("bltailmerge()\n");
    assert(!PARSER && OPTIMIZER);
    if (!(mfoptim & MFtime))		/* if optimized for space	*/
    {
	block *b;
	block *bn;
	list_t bl;
	elem *e;
	elem *en;

	/* Split each block into a reversed linked list of elems	*/
	for (b = startblock; b; b = b->Bnext)
	    b->Blist = bl_enlist(b->Belem);

	/* Search for two blocks that have the same successor list.
	   If the first expressions both lists are the same, split
	   off a new block with that expression in it.
	 */
	for (b = startblock; b; b = b->Bnext)
	{
	    if (!b->Blist)
		continue;
	    e = list_elem(b->Blist);
	    elem_debug(e);
	    for (bn = b->Bnext; bn; bn = bn->Bnext)
	    {
		if (b->BC == bn->BC &&
		    list_equal(b->Bsucc,bn->Bsucc) &&
		    bn->Blist &&
		    el_match(e,(en = list_elem(bn->Blist)))
#if SCPP || NTEXCEPTIONS
		    && b->Btry == bn->Btry
#endif
		   )
		{
		    switch (b->BC)
		    {
			case BCswitch:
			    if (memcmp(b->BS.Bswitch,bn->BS.Bswitch,list_nitems(bn->Bsucc) * sizeof(*bn->BS.Bswitch)))
				continue;
			    break;

#if SCPP
			case BCtry:
			case BCcatch:
#endif
#if MARS
			case BCjcatch:
#endif
			case BC_try:
			case BC_finally:
			case BCasm:
			    continue;
		    }

		    /* We've got a match	*/
		    block *bnew;

		    /*	Create a new block, bnew, which will be the
			merged block. Physically locate it just after bn.
		     */
#ifdef DEBUG
		    if (debugc)
			dbg_printf("tail merging: %p and %p\n", b, bn);
#endif
		    numblks++;
		    bnew = block_calloc();
		    bnew->Bnext = bn->Bnext;
		    bnew->BC = b->BC;
#if SCPP || NTEXCEPTIONS
		    bnew->Btry = b->Btry;
#endif
		    if (bnew->BC == BCswitch)
		    {
			bnew->BS.Bswitch = b->BS.Bswitch;
#if !HOST_THINK
			MEM_PH_FREE(bn->BS.Bswitch);
#endif
			b->BS.Bswitch = NULL;
			bn->BS.Bswitch = NULL;
		    }
		    bn->Bnext = bnew;

		    /* The successor list to bnew is the same as b's was */
		    bnew->Bsucc = b->Bsucc;
		    b->Bsucc = NULL;
		    list_free(&bn->Bsucc,FPNULL);

		    /* Update the predecessor list of the successor list
			of bnew, from b to bnew, and removing bn
		     */
		    for (bl = bnew->Bsucc; bl; bl = list_next(bl))
		    {
			list_subtract(&list_block(bl)->Bpred,b);
			list_subtract(&list_block(bl)->Bpred,bn);
			list_append(&list_block(bl)->Bpred,bnew);
		    }

		    /* The predecessors to bnew are b and bn	*/
		    list_append(&bnew->Bpred,b);
		    list_append(&bnew->Bpred,bn);

		    /* The successors to b and bn are bnew	*/
		    b->BC = BCgoto;
		    bn->BC = BCgoto;
		    list_append(&b->Bsucc,bnew);
		    list_append(&bn->Bsucc,bnew);

		    changes++;

		    /* Find all the expressions we can merge	*/
		    do
		    {
			list_append(&bnew->Blist,e);
			el_free(en);
			list_pop(&b->Blist);
			list_pop(&bn->Blist);
			if (!b->Blist)
			    goto nextb;
			e = list_elem(b->Blist);
			if (!bn->Blist)
			    break;
			en = list_elem(bn->Blist);
		    } while (el_match(e,en));
		}
	    }
    nextb:  ;
	}

	/* Recombine elem lists into expression trees	*/
	for (b = startblock; b; b = b->Bnext)
	    b->Belem = bl_delist(b->Blist);
    }
}

/**********************************
 * Rearrange blocks to minimize jmp's.
 */

STATIC void brmin()
{   block *b;
    block *bnext;
    list_t bl,blp;

#if SCPP
    // Dunno how this may mess up generating EH tables.
    if (config.flags3 & CFG3eh)		// if EH turned on
	return;
#endif

    cmes("brmin()\n");
    debug_assert(startblock);
    for (b = startblock->Bnext; b; b = b->Bnext)
    {
	bnext = b->Bnext;
	if (!bnext)
	    break;
	for (bl = b->Bsucc; bl; bl = list_next(bl))
	{   block *bs;

	    bs = list_block(bl);
	    if (bs == bnext)
		goto L1;
	}

	// b is a block which does not have bnext as a successor.
	// Look for a successor of b for which everyone must jmp to.

	for (bl = b->Bsucc; bl; bl = list_next(bl))
	{   block *bs;
	    block *bn;

	    bs = list_block(bl);
	    for (blp = bs->Bpred; blp; blp = list_next(blp))
	    {	block *bsp;

		bsp = list_block(blp);
		if (bsp->Bnext == bs)
		    goto L2;
	    }

	    // Move bs so it is the Bnext of b
	    for (bn = bnext; 1; bn = bn->Bnext)
	    {
		if (!bn)
		    goto L2;
		if (bn->Bnext == bs)
		    break;
	    }
#if 1
	    bn->Bnext = NULL;
	    b->Bnext = bs;
	    for (bn = bs; bn->Bnext; bn = bn->Bnext)
		;
	    bn->Bnext = bnext;
#else
	    bn->Bnext = bs->Bnext;
	    bs->Bnext = bnext;
	    b->Bnext = bs;
#endif
	    cmes3("Moving block %p to appear after %p\n",bs,b);
	    changes++;
	    break;

	L2: ;
	}


    L1:	;
    }
}

/********************************
 * Check integrity of blocks.
 */

#if 0

STATIC void block_check()
{   block *b;
    list_t bl;

    for (b = startblock; b; b = b->Bnext)
    {	int nsucc;
	int npred;

	nsucc = list_nitems(b->Bsucc);
	npred = list_nitems(b->Bpred);
	switch (b->BC)
	{
	    case BCgoto:
		assert(nsucc == 1);
		break;
	    case BCiftrue:
		assert(nsucc == 2);
		break;
	}

	for (bl = b->Bsucc; bl; bl = list_next(bl))
	{   block *bs = list_block(bl);
	    list_t bls;

	    for (bls = bs->Bpred; 1; bls = list_next(bls))
	    {
		assert(bls);
		if (list_block(bls) == b)
		    break;
	    }
	}
    }
}

#endif

/***************************************
 * Do tail recursion.
 */

STATIC void brtailrecursion()
{   block *b;
    block *bn;
    block *bs;
    list_t bl;
    elem **pe;

#if SCPP
//    if (tyvariadic(funcsym_p->Stype))
	return;
    return;		// haven't dealt with struct params, and ctors/dtors
#endif
    if (funcsym_p->Sfunc->Fflags3 & Fnotailrecursion)
	return;
    if (localgot)
    {	/* On OSX, tail recursion will result in two OPgot's:
	    int status5;
	    struct MyStruct5 { }
	    void rec5(int i, MyStruct5 s)
	    {
		if( i > 0 )
		{   status5++;
		    rec5(i-1, s);
		}
	    }
	*/ 

	return;
    }
    for (b = startblock; b; b = b->Bnext)
    {
	if (b->BC == BC_try)
	    return;
	pe = &b->Belem;
	if (*pe &&
	    (b->BC == BCret ||
	     b->BC == BCretexp ||
	     (b->BC == BCgoto && (bn = list_block(b->Bsucc))->Belem == NULL &&
	      bn->BC == BCret)
	    )
	   )
	{   elem *e;

	    if (el_anyframeptr(*pe))
		return;
	    while ((*pe)->Eoper == OPcomma)
		pe = &(*pe)->E2;
	    e = *pe;
	    if (OTcall(e->Eoper) &&
		e->E1->Eoper == OPvar &&
		e->E1->EV.sp.Vsym == funcsym_p)
	    {
//printf("before:\n");
//elem_print(*pe);
		if (OTunary(e->Eoper))
		{   *pe = el_long(TYint,0);
		}
		else
		{   int si = 0;
		    elem *e2 = NULL;
		    *pe = assignparams(&e->E2,&si,&e2);
		    *pe = el_combine(*pe,e2);
		}
		el_free(e);
//printf("after:\n");
//elem_print(*pe);

		if (b->BC == BCgoto)
		{   list_subtract(&b->Bsucc,bn);
		    list_subtract(&bn->Bpred,b);
		}
		b->BC = BCgoto;
		list_append(&b->Bsucc,startblock);
		list_append(&startblock->Bpred,b);

		// Create a new startblock, bs, because startblock cannot
		// have predecessors.
		numblks++;
		bs = block_calloc();
		bs->BC = BCgoto;
		bs->Bnext = startblock;
		list_append(&bs->Bsucc,startblock);
		list_append(&startblock->Bpred,bs);
		startblock = bs;

		cmes("tail recursion\n");
		changes++;
		return;
	    }
	}
    }
}

/*****************************************
 * Convert parameter expression to assignment statements.
 */

STATIC elem * assignparams(elem **pe,int *psi,elem **pe2)
{
    elem *e = *pe;

    if (e->Eoper == OPparam)
    {	elem *ea = NULL;
	elem *eb = NULL;
	elem *e2 = assignparams(&e->E2,psi,&eb);
	elem *e1 = assignparams(&e->E1,psi,&ea);
	e->E1 = NULL;
	e->E2 = NULL;
	e = el_combine(e1,e2);
	*pe2 = el_combine(eb,ea);
    }
    else
    {	int si = *psi;
	Symbol *sp;
	Symbol *s;
	int op;
	unsigned numbytes;
	elem *es;

	assert(si < globsym.top);
	sp = globsym.tab[si];
	s = symbol_genauto(sp->Stype);
	s->Sfl = FLauto;
	op = OPeq;
	if (e->Eoper == OPstrpar)
	{   elem *ex;

	    op = OPstreq;
	    numbytes = e->Enumbytes;
	    ex = e;
	    e = e->E1;
	    ex->E1 = NULL;
	    el_free(ex);
	}
	es = el_var(s);
	es->Ety = e->Ety;
	e = el_bin(op,TYvoid,es,e);
	if (op == OPstreq)
	    e->Enumbytes = numbytes;
	*pe2 = el_bin(op,TYvoid,el_var(sp),el_copytree(es));
	(*pe2)->E1->Ety = es->Ety;
	if (op == OPstreq)
	    (*pe2)->Enumbytes = numbytes;
	*psi = ++si;
	*pe = NULL;
    }
    return e;
}

/****************************************************
 * Eliminate empty loops.
 */

STATIC void emptyloops()
{
    block *b;

    cmes("emptyloops()\n");
    for (b = startblock; b; b = b->Bnext)
    {
	if (b->BC == BCiftrue &&
	    list_block(b->Bsucc) == b &&
	    list_nitems(b->Bpred) == 2)
	{   block *bpred;
	    elem *einit;
	    elem *erel;
	    elem *einc;

	    // Find predecessor to b
	    bpred = list_block(b->Bpred);
	    if (bpred == b)
		bpred = list_block(list_next(b->Bpred));
	    if (!bpred->Belem)
		continue;

	    // Find einit
	    for (einit = bpred->Belem; einit->Eoper == OPcomma; einit = einit->E2)
		;
	    if (einit->Eoper != OPeq ||
		einit->E2->Eoper != OPconst ||
		einit->E1->Eoper != OPvar)
		continue;

#if 1
	    // Look for ((i += 1) < limit)
	    erel = b->Belem;
	    if (erel->Eoper != OPlt ||
		erel->E2->Eoper != OPconst ||
		erel->E1->Eoper != OPaddass)
		continue;

	    einc = erel->E1;
	    if (einc->E2->Eoper != OPconst ||
		einc->E1->Eoper != OPvar ||
		!el_match(einc->E1,einit->E1))
		continue;

	    if (!tyintegral(einit->E1->Ety) ||
		el_tolong(einc->E2) != 1 ||
		el_tolong(einit->E2) >= el_tolong(erel->E2)
	       )
		continue;

	     {
		erel->Eoper = OPeq;
		erel->Ety = erel->E1->Ety;
		erel->E1 = el_selecte1(erel->E1);
		b->BC = BCgoto;
		list_subtract(&b->Bsucc,b);
		list_subtract(&b->Bpred,b);
#ifdef DEBUG
		if (debugc)
		{   WReqn(erel);
		    dbg_printf(" eliminated loop\n");
		}
#endif
		changes++;
	     }
#else
	    // Find einc and erel
	    if (b->Belem->Eoper != OPcomma)
		continue;
	    einc = b->Belem->E1;
	    erel = b->Belem->E2;
	    if (einc->Eoper != OPaddass ||
		einc->E1->Eoper != OPvar ||
		einc->E2->Eoper != OPconst ||
		erel->Eoper != OPlt ||
		erel->E1->Eoper != OPvar ||
		erel->E2->Eoper != OPconst ||
		!el_match(einit->E1,einc->E1) ||
		!el_match(einit->E1,erel->E1)
	       )
		continue;

	    if (!tyintegral(einit->E1->Ety) ||
		el_tolong(einc->E2) != 1 ||
		el_tolong(einit->E2) >= el_tolong(erel->E2)
	       )
		continue;

	     {
		erel->Eoper = OPeq;
		erel->Ety = erel->E1->Ety;
		b->BC = BCgoto;
		list_subtract(&b->Bsucc,b);
		list_subtract(&b->Bpred,b);
#ifdef DEBUG
		if (debugc)
		{   WReqn(erel);
		    dbg_printf(" eliminated loop\n");
		}
#endif
		changes++;
	     }
#endif
	}
    }
}

/******************************************
 * Determine if function has any side effects.
 * This means, determine if all the function does is return a value;
 * no extraneous definitions or effects or exceptions.
 * A function with no side effects can be CSE'd. It does not reference
 * statics or indirect references.
 */

STATIC int funcsideeffect_walk(elem *e);

void funcsideeffects()
{
#if MARS
    block *b;

    //printf("funcsideeffects('%s')\n",funcsym_p->Sident);
    for (b = startblock; b; b = b->Bnext)
    {
	if (b->Belem && funcsideeffect_walk(b->Belem))
	    goto Lside;
    }

Lnoside:
    funcsym_p->Sfunc->Fflags3 |= Fnosideeff;
    //printf("  function '%s' has no side effects\n",funcsym_p->Sident);
    //return;

Lside:
    //printf("  function '%s' has side effects\n",funcsym_p->Sident);
    ;
#endif
}

#if MARS

STATIC int funcsideeffect_walk(elem *e)
{   int op;
    Symbol *s;

    assert(e);
    elem_debug(e);
    if (typemask(e) & mTYvolatile)
	goto Lside;
    op = e->Eoper;
    switch (op)
    {
	case OPcall:
	case OPucall:
	    if (e->E1->Eoper == OPvar &&
		tyfunc((s = e->E1->EV.sp.Vsym)->Stype->Tty) &&
		((s->Sfunc && s->Sfunc->Fflags3 & Fnosideeff) || s == funcsym_p)
	       )
		break;
	    goto Lside;

	case OParray:
	case OPfield:
	    goto Lside;			// these can throw exceptions

	// Note: we should allow assignments to local variables as
	// not being a 'side effect'.

	default:
	    assert(op < OPMAX);
	    return OTsideff(op) ||
		(OTunary(op) && funcsideeffect_walk(e->E1)) ||
		(OTbinary(op) && (funcsideeffect_walk(e->E1) ||
				  funcsideeffect_walk(e->E2)));
    }
    return 0;

  Lside:
    return 1;
}

#endif

/*******************************
 * Determine if there are any OPframeptr's in the tree.
 */

int el_anyframeptr(elem *e)
{
    while (1)
    {
	if (OTunary(e->Eoper))
	    e = e->E1;
	else if (OTbinary(e->Eoper))
	{   if (el_anyframeptr(e->E2))
		return 1;
	    e = e->E1;
	}
	else if (e->Eoper == OPframeptr)
	    return 1;
	else
	    break;
    }
    return 0;
}


#endif //!SPP
